package com.sxt;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**基于树形结构实现元素存储的容器*/
/*树形结构的定义：满足以下5点（注：根结点只子孙与子节点）
（叶子结点没有子结点 有兄弟、父、祖先结点）
* 能够找到当前结点的父结点     能够找到当前结点的子结点
* 能够找到当前结点的兄弟结点   能够找到当前结点的祖先结点
* 能够找到当前结点的子孙结点*/
    /*用Map 与List 容器存储  Map的key,List多个  实现一对多*/
public class MyTree<E> {
    //创建两Map  一个用于方便查父结点  一个方便用于查子结点
    private Map<E,E> map = new HashMap<>();//key:String,value:String
    private Map<E,List<E>> map2 = new HashMap<>();//String  List<String>



    /*向容器中添加元素*/
    //一个是父结点，一个是添加的元素
    public void add(E parent,E item){
        //先完成单节点之间的映射 方便获取父结点 (由下往上)
       this.map.put(item,parent);
       /*根据父结点取出子结点*/
       //完成多节点之间的映射  方便获取子结点（由上往下）  多节点要用List<E>容器
        List<E> list = this.map2.get(parent);
        //判断当前结点下是否有子结点，如果没有则创建一个新的list
        if(list == null){
            //第一次添加时，可能没有子结点
            list = new ArrayList<>();
            this.map2.put(parent,list);
        }
        list.add(item);
    }
    //获取当前结点的父结点
    public E getParent(E item){

        return this.map.get(item);
    }
    //获取当前结点的子结点  可能有多个子结点，所以用List容器存储
    public List<E> getChild(E item){

        return this.map2.get(item);
    }
    //获取当前结点的兄弟结点
    public List<E> getBrother(E item){
        //获取当前结点的父结点
        E parent = this.map.get(item);
        //获取当前结点的子结点
        List<E> list = this.getChild(parent);
        /*不可以用list.remove()直接删除当前结点，因为会把这树形结构
        * 的结点删除了，所以要新创建一个List，再删除除*/
        List<E> brother = new ArrayList<>();

        if(list != null){
            /*取并集*/
            brother.addAll(list);
            brother.remove(item);
        }
        return brother;
    }
    //获取当前结点的的祖先结点
    public List<E> getForefather(E item){
        //获取当前结点的父结点
        E parent= this.getParent(item);
        //在递归前添加结束边界条件，
        /*当所有的父结点都递归完才执行下面的
        List<E> list = this.getForefather(parent);*/
        if( parent == null){
            //new ArrayList 是上面方法返回的List<E>也是下面的List
            return new ArrayList<>();
        }
        //递归调用，再次获取当前结点的父结点
        List<E> list = this.getForefather(parent);
        //将递归到的所有结点元素添加到返回的list 中
        list.add(parent);
        return list;
    }
    //获取当前结点的子孙结点
    public List<E>  getGrandChildren(E item){
        //存放所有子孙结点中的元素
        List<E> list = new ArrayList<>();
        //获取当前结点的子结点
        List<E> child = this.getChild(item);
        if(child ==null)return list;
        //遍历子结点
        for (int i =0;i<child.size();i++){
            //获取节点中的元素
            E ele = child.get(i);
            //递归
            List<E> tem = this.getGrandChildren(ele);
            list.add(ele);
            list.addAll(tem);
        }
        return list;
    }

    public static void main(String[] args) {
        //实例化容器
        MyTree<String> myTree = new MyTree<>();
        myTree.add("root","生物");
        myTree.add("生物","植物");
        myTree.add("生物","动物");
        myTree.add("生物","菌类");
        myTree.add("动物","脊椎动物");
        myTree.add("动物","脊索动物");
        myTree.add("动物","腔肠动物物");
        myTree.add("脊椎动物","哺乳动物");
        myTree.add("脊椎动物","鱼");
        myTree.add("哺乳动物","猫");
        myTree.add("哺乳动物","牛");
        myTree.add("哺乳动物","人");
        System.out.println("-----获取父节点------");
        String parent = myTree.getParent("鱼");
        System.out.println(parent);
        System.out.println("-------获取子结点----");
        List<String> child = myTree.getChild("动物");
        for(int i=0;i< child.size();i++){
            System.out.println(child.get(i));
        }
        System.out.println("-------获取兄弟结点----");
        List<String> brother = myTree.getBrother("脊椎动物");
        for(int i=0;i<brother.size();i++){
            System.out.println(brother.get(i));
        }
        System.out.println("-------获取祖先结点----");
        List<String> forFather = myTree.getForefather("人");
        for(int i=0;i<forFather.size();i++){
            System.out.println(forFather.get(i));
        }
        System.out.println("-------获取子孙结点----");
        List<String> grandChildren = myTree.getGrandChildren("root");
        for(int i=0;i<grandChildren.size();i++){
            System.out.println(grandChildren.get(i));
        }
    }
}
